package cn.edu.xjtu.算法刷题计划.算法基础;

/**
 * 34. 在排序数组中查找元素的第一个和最后一个位置
 * 
 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 * 
 * 如果数组中不存在目标值 target，返回 [-1, -1]。
 * 
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public static void main(String[] args) {
        Solution solu = new Solution();
        int[] nums = { 1 };
        int target = 1;
        System.out.println(solu.searchRange(nums, target));
    }

    /**
     * 利用二分法分别查找该元素的一个以及大于该元素的第一个
     * 
     * @param nums
     * @param target
     * @return
     */
    public int[] searchRange(int[] nums, int target) {
        int[] ret = { -1, -1 };
        if (nums.length == 0) {
            return ret;
        }
        int left = searchHelp(nums, target, true);
        int right = searchHelp(nums, target, false) - 1;
        if (left <= right && left != nums.length && right != nums.length && nums[left] == target
                && nums[right] == target) {
            ret[0] = left;
            ret[1] = right;
        }
        return ret;
    }

    private int searchHelp(int[] nums, int target, boolean equal) {
        int left = 0;
        int right = nums.length - 1;
        int ans = nums.length;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target || (equal && nums[mid] == target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

    /**
     * 利用二分找到该元素,然后向左向右遍历,直到查找到不是该元素的第一个
     * 
     * @param nums
     * @param target
     * @return
     */
    public int[] searchRange1(int[] nums, int target) {
        int[] ret = { -1, -1 };

        if (nums.length == 0) {
            return ret;
        }
        int left = 0;
        int right = nums.length - 1;
        int mid = 0;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                break;
            }
        }
        if (left > right) {
            return ret;
        }
        left = mid;
        right = mid;
        while (left >= 0 && nums[left] == target) {
            left--;
        }
        while (right <= nums.length - 1 && nums[right] == target) {
            right++;
        }
        ret[0] = left + 1;
        ret[1] = right - 1;
        return ret;
    }
}
